package com.xiaoyu.arrays;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: DS_and_A
 * @description: 杨辉三角2
 * 给定一个非负索引k，其中 k≤33，返回杨辉三角的第 k 行。
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 *
 * 示例:
 *
 * 输入: 3
 * 输出: [1,3,3,1]
 *
 * 你可以优化你的算法到 O(k) 空间复杂度吗？
 *
 * @author: YuWenYi
 * @create: 2021-05-27 16:43
 **/
public class YangHuiTriangle2_119 {

    public static List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        if (rowIndex < 0) return res;
        res.add(1);
        if (rowIndex == 0) return res;
        res.add(1);
        if (rowIndex == 1) return res;

        List<Integer> temp = new ArrayList<>(res);
        for (int i = 2; i <= rowIndex; i++) {  //从第三行开始
            for (int j = 0; j <= i; j++) {
                Integer num1 = j > temp.size()-1 ? 0 : temp.get(j); //获取上一行当前索引的值
                Integer num2 = j - 1 < 0 ? 0 : temp.get(j-1);  //获取上一行当前索引-1的值
                if (j == temp.size()){
                    res.add(num1+num2);
                }else {
                    res.set(j,num1+num2);
                }
            }
            temp = new ArrayList<>(res);
        }
        return res;
    }

    public List<Integer> getRow1(int rowIndex) {
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> cur = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                //使用这种方法去排除两端更优雅
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }

    //方法三:当前行第 i 项的计算只与上一行第 i-1 项及第 i 项有关。
    //因此我们可以倒着计算当前行，这样计算到第 i 项时，第 i-1 项仍然是上一行的值。
    public static List<Integer> getRow2(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        res.add(1);
        if (rowIndex == 0) return res;
        for (int i = 1; i <= rowIndex; i++) {
            res.add(0);  //每次新增一行,就添个0补位
            //从后往前去set,假设set第5位的值,那么在set之前0,1,2,3,4,5上的值都是上一行的值,
            //在set的之后,0,1,2,3,4依旧是上一行的值,这说明从后往前set就能以最简洁的方法获取第N行
            for (int j = i; j > 0; j--) {
                res.set(j, res.get(j)+res.get(j-1));
            }
        }
        return res;
    }


    public static void main(String[] args) {
        List<Integer> row = getRow2(5);
        System.out.println(row);
    }
}
